#include <stdio.h>

/* ¹©²Î¿¼£¬ÓÃÓÚÓÃÓ¢ÎÄµÄ¿Õ¸ñ·Ö¸ô£¬ÒÀ´Î°ÑÊý×éÄÚµÄÔªËØµÄÖµ´òÓ¡µ½±ê×¢Êä³ö£¬²¢ÔÚÐÐÄ©¸½¼ÓÒ»¸ö»»ÐÐ·û*/
void print_array(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
/*
    Íê³ÉÅÅÐòºóµÄÊý×é¾ùÍ¨¹ýunsorted_array·µ»Ø£»
    Èý¸öº¯ÊýÉùÃ÷ÖÐ£¬num_elementsÎª´ýÅÅÐòµÄÔªËØ¸öÊý¡£
    ¿É¸ù¾ÝÐèÒª×ÔÐÐÌí¼ÓÆäËûº¯Êý¡£
*/

/*´ýÅÅÐòµÄÊý×éÔªËØµÄ±àºÅ´Ó0¿ªÊ¼µ½num_elements-1¡£
ÒªÇó£º
1.	ÊµÏÖÈçÏÂÉùÃ÷µÄinsertion_sortº¯Êý¡£
2.	ÔÚ°Ñ´Ó1µ½num_elements-1Î»ÖÃÉÏµÄÃ¿¸öÔªËØ·ÅÖÃµ½ºÏÊÊÎ»ÖÃÉÏÖ®ºó£¬½«´ËÊ±unsorted_arrayÀïµÄÈ«²¿ÔªËØµÄÖµ´òÓ¡µ½±ê×¼Êä³ö£¬ÔªËØÖµÖ®¼ä½öÓÃÓ¢ÎÄµÄ¿Õ¸ñ·Ö¸ô£¬Ã¿´ÎÊä³ö Ö®ºó»»ÐÐ¡£±ÈÈçÊäÈëµÄunsorted_arrayÊý×éÀïÒÀ´Î°üº¬4¸öÔªËØ4, 3, 2, 1¡£ÄÇÃ´Êä³öµÄÄÚÈÝÓ¦¸ÃÈçÏÂ£º
3 4 2 1
2 3 4 1
1 2 3 4

*/
void insertion_sort(int unsorted_array[], int num_elements){
    for (int j = 1; j < num_elements; j++) {
        int key = unsorted_array[j];
        int i = j - 1;
        while (i >= 0 && key < unsorted_array[i]) {
            unsorted_array[i + 1] = unsorted_array[i];
            i--;
        }
        unsorted_array[i + 1] = key;
        print_array(unsorted_array,num_elements);
    }
}


/*´ýÅÅÐòµÄÊý×éÔªËØµÄ±àºÅ´Ó0¿ªÊ¼µ½total_num_elements-1¡£
ÒªÇó£º
1.	ÊµÏÖÈçÏÂÉùÃ÷µÄpartitionº¯Êý£»ÓÀÔ¶Ñ¡ÔñlowÎ»ÖÃÉÏµÄÔªËØ×÷ÎªpivotÖ§³ÅÔªËØ£»ÔÚpartitionº¯Êý·µ»ØpivotÖ§³ÅÔªËØµÄÎ»ÖÃÖ®Ç°£¬°Ñunsorted_arrayÀïµÄËùÓÐÔªËØµÄÖµ´òÓ¡µ½±ê×¼Êä³ö£¬ÔªËØÖµÖ®¼ä½öÓÃÓ¢ÎÄµÄ¿Õ¸ñ·Ö¸ô£¬Ã¿´ÎÊä³ö Ö®ºó»»ÐÐ¡£
2.	µÝ¹éÊµÏÖÈçÏÂÉùÃ÷µÄquick_sortº¯Êý£»ÔÚÃ¿´ÎµÝ¹éÊ±ÏÈ´¦Àí×ó²àµÄ×ÓÊý×é£¬ÔÙ´¦ÀíÓÒ²àµÄ×ÓÊý×é£»quick_sort±ØÐëµ÷ÓÃpartitionº¯Êý»ñÈ¡pivotÖ§³ÅÔªËØµÄÎ»ÖÃ¡£
3.	±ÈÈçµ±ÊäÈëµÄunsorted_arrayÊý×éµÄÔªËØÒÀ´ÎÎª 3, 1, 2, 5, 4Ê±£¬Êä³öÓ¦¸ÃÎª£º
2 1 3 5 4
1 2 3 5 4
1 2 3 4 5

*/
int partition(int L[], int low,  int  high, int total_num_elements){//·Ö¸î
    int temp = L[low];
    int pivot = L[low];
    while(low < high){
        while(low < high&&L[high] >= pivot){
            --high;
        }
        L[low] = L[high];
        while(low < high && L[low] <= pivot){
            ++low;
        }
        L[high]=L[low];
    }
    L[low] = temp;
    print_array(L,total_num_elements);
    return low;
}
void QSort(int L[], int low,  int  high, int total_num_elements){
    if(low < high){
        int  pivotpos = partition(L,low,high,total_num_elements);

        QSort(L,low,pivotpos-1,total_num_elements);
        QSort(L,pivotpos+1,high,total_num_elements);

    }
}

void quick_sort(int unsorted_array[],int num_elements ){
    int low = 0,high = num_elements-1;
    QSort(unsorted_array,low,high,num_elements);
}


/*
´ýÅÅÐòµÄÊý×éÔªËØµÄ±àºÅ´Ó0¿ªÊ¼µ½num_elements-1
ÒªÇó£º
1.	ÊµÏÖÈçÏÂÉùÃ÷µÄheap_sortº¯Êý¡£
2.	ÔÚÃ¿´Î¶ÔÒÑ¾­½¨ºÃµÄ×î´ó¶Ñ½øÐÐµ÷ÕûÈ»ºó°Ñµ±Ç°¸ùÀïµÄ×î´óÖµ·ÅÖÃµ½ºÏÊÊÕýÈ·µÄÎ»ÖÃÖ®ºó¡¢ÔÙ´Îµ÷ÕûÐÎ³É×î´ó¶ÑÖ®Ç°£¬°Ñunsorted_arrayÀïµÄËùÓÐÔªËØµÄÖµ´òÓ¡µ½±ê×¼Êä³ö£¬ÔªËØÖµÖ®¼ä½öÓÃÓ¢ÎÄµÄ¿Õ¸ñ·Ö¸ô£¬Ã¿´ÎÊä³öÖ®ºó»»ÐÐ¡£ÀýÈç£º
10 60 12 40 30 8 70
8 40 12 10 30 60 70
8 30 12 10 40 60 70
8 10 12 30 40 60 70
8 10 12 30 40 60 70
8 10 12 30 40 60 70
*/

void max_heap_down(int a[], int start, int end)
{
    int c = start;
    int l = 2 * c + 1;//startµÄ×óº¢×ÓË÷Òý
    int tmp = a[c];
    for (; l <= end; c = l, l = 2 * l + 1)//½«cÉèÖÃÎªÆä×óº¢×Ó£¬lÉèÖÃÎªÓÒº¢×Ó
    {
        if (l < end && a[l] < a[l + 1])//Èç¹ûÓÒº¢×ÓÐ¡ÓÚend£¬²¢ÇÒ,ÓÒº¢×ÓÐ¡ÓÚ×óº¢×Ó
            l++;       //½«l¸ÄÎª×óº¢×ÓË÷Òý
        if (tmp >= a[l])//Èç¹ûcµÄº¢×ÓÖÐ½Ï´óµÄÔªËØ´óÓÚ¸¸Ç×½Úµã
            break;   //ÔòÌø³öÑ­»·
        else           //·ñÔò
        {
            a[c] = a[l];//½«¸¸Ç×½ÚµãºÍ±È×Ô¼º´óµÄº¢×Ó½áµã½»»»
            a[l] = tmp;
        }
    }
}
void heap_sort(int unsorted_array[], int num_elements){
    int i;
    int swap;
    for (i = num_elements / 2 - 1; i >= 0; i--)
        max_heap_down(unsorted_array, i, num_elements - 1);
    for (i = num_elements - 1; i > 0; i--)//ÉèÖÃn-1´ÎÑ­»·£¬ÒòÎªµ±n-1¸ö½Úµã¶¼°´Ë³ÐòÅÅºÃÒÔºó£¬×îºóÒ»¸öÒ»¶¨ÊÇ×îÐ¡Öµ
    {   swap=unsorted_array[i];
        unsorted_array[i]=unsorted_array[0];
        unsorted_array[0]=swap;
        print_array(unsorted_array,num_elements);
        max_heap_down(unsorted_array, 0, i - 1);
    }
}
void main(){
    int test[10]={4,3,2,1};
    insertion_sort( test, 4);
    printf("\n");
    int test1[10]={3,1,2,5,4};
    QSort(test1,0,4,5);
    printf("\n");
    int test2[10]={10,60,12,40,30,8,70};
    heap_sort(test2,7);
}